import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class SortGapMax {
    /**
     * 计算相邻的两个数之间的最大值
     * @param args
     */
    public static void main(String[] args) {
        // 准备条件
        Scanner in=new Scanner(System.in);
        System.out.print("请输入数组的长度：");
        int n= in.nextInt();
        System.out.println("请依次输入数组的元素：");
        Double []a= new Double[n];
        for(int i=0;i<n;i++){
            a[i]= in.nextDouble();
        }

        // 首先需要对元素进行排序，时间复杂度为O(nlog(n))
//        Arrays.sort(a);

        // 改成快速排序
        quickSort(a, 0, n - 1);
        System.out.println("排序后的数组为："+ Arrays.toString(a));

        // 定义间隔的值
        double gap=0;
        for(int i=1;i<n;i++){
            gap= Math.max(gap,a[i]-a[i-1]);
        }
        System.out.println("数组中的最大间隙："+gap);
    }

    // 快速排序算法
    public static void quickSort(Double[] arr,int low,int high){
        if(low<high){
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 分区函数
    public static int partition(Double[] arr,int low,int high){
        // 定义右边界为此时的主元
        double pivot=arr[high];
        // 称之为交换位，i此时指向为空，交换的时候+1指向需要的位置
        int i=low-1;
        for(int j=low;j<high;j++){
            // 称j为移动指针，用于判断当前位置元素和主元的关系
            if(arr[j]>=pivot){ //此时是左侧大，右侧小
                // 此时i指向上一位交换的元素，交换
                i++;
                swap(arr,i,j);
            }
        }
        // 最后的位置是此时的主元的下标，此时交换之后得到的：主元左侧数字小于主元，右侧大于主元
        swap(arr,i+1,high);
        return i+1;
    }

    // 交换元素
    public static void swap(Double[] arr,int i,int j){
        double tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
}
